#include <iostream>
#include <functional>
#include <vector>
#include <memory>

class LazyTree {
	std::vector<int> _data;
	std::vector<int> _lazy;
	int _n = 0;
public:
	LazyTree(int n) : _n {n} {
		init();
	}
	LazyTree(const std::vector<int>& data) {
		_n = data.size();
		init();
		build(0, _n - 1, 0, data);
	}
	// 对区间内的数据统一增加(减少)num
	void add(int L, int R, int num) {
		std::function<void(int, int, int)> dfs = [&](int left, int right, int pos) {
			if (L <= left && right <= R) {
				update(left, right, pos, num);
				return;
			}
			int mid = (left + right) / 2;
			if (_lazy[pos]) {
				update(left, mid, 2 * pos + 1, _lazy[pos]);
				update(mid + 1, right, 2 * pos + 2, _lazy[pos]);
				_lazy[pos] = 0;
			}
			if (L <= mid) dfs(left, mid, 2 * pos + 1);
			if (mid + 1 <= R) dfs(mid + 1, right, 2 * pos + 2);
			maintain(left, right, pos);
		};
		dfs(0, _n - 1, 0);
	}
	// 查找区间内的总数
	int find(int L, int R) {
		std::function<int(int, int, int)> dfs = [&](int left, int right, int pos) -> int {
			if (L <= left && right <= R) {
				return _data[pos];
			}
			int mid = (left + right) / 2;
			if (_lazy[pos]) {
				update(left, mid, 2 * pos + 1, _lazy[pos]);
				update(mid + 1, right, 2 * pos + 2, _lazy[pos]);
				_lazy[pos] = 0;
			}
			int res = 0;
			if (L <= mid) res += dfs(left, mid, 2 * pos + 1);
			if (mid + 1 <= R) res += dfs(mid + 1, right, 2 * pos + 2);
			maintain(left, right, pos);
			return res;
		};
		return dfs(0, _n - 1, 0);
	}
private:
	// 初始化, 根据数学推算，线段树实际大小 <= 原数组大小 * 4
	void init() {
		_data = std::move(std::vector<int>(_n * 4));
		_lazy = std::move(std::vector<int>(_n * 4));
	}
	// 计算出当前结点的数据大小，并且将lazy标记，避免暴力
	void update(int left, int right, int pos, int num) {
		_data[pos] += (right - left + 1) * num;
		_lazy[pos] += num;
	}
	// 维护线段树: 将两个子结点的值给父结点，保证当前父结点的data是正确的
	void maintain(int left, int right, int pos) {
		_data[pos] = _data[2 * pos + 1] + _data[2 * pos + 2];
	}
	// 构建线段树
	void build(int left, int right, int pos, const std::vector<int>& data) {
		if (left == right) {
			_data[pos] = data[left];
			return;
		}
		int mid = (left + right) / 2;
		build(left, mid, 2 * pos + 1, data);
		build(mid + 1, right, 2 * pos + 2, data);
		maintain(left, right, pos);
	}
};

int main() {
	std::vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8};
	auto lt = std::make_unique<LazyTree>(arr);
	std::cout << lt->find(1, 6) << std::endl;
	lt->add(2, 5, 2);
	std::cout << lt->find(1, 6) << std::endl;
}